Propositional Logic

Number Sets

R=\SetAll decimal representations =QQc\Bbb{R}=\Set{All\space decimal\space representations\space } = \Bbb{Q}\cup \Bbb{Q}^c = real numbers

Z={...,2,1,0,1,2,3...}\Bbb{Z}=\{...,-2,-1,0,1,2,3...\} = integers

N=Z+={1,2,3...}\Bbb{N}=\Bbb{Z}^+=\{1,2,3...\} = positive integers

Q={f/qp,qZ,q0,p and q have no common factors}\Bbb{Q}=\{f/q\mid p, q\in\Bbb{Z},q\neq 0, p\space and\space q\space have\space no\space common\space factors \} = rational numbers

Qc={xRxQ}\Bbb{Q}^c=\{x\in \Bbb{R}\mid x\notin\Bbb{Q}\} = irrational numbers

C=\setx+igx,yR and i2=1\Bbb{C} =\set{x+ig\mid x,y\in \Bbb{R}\space and\space i^2=-1} = Complex numbers

Use the math directive
If DZD\in\Bbb{Z} set of integers

wt+1=(1+rt+1)s(wt)+yt+1 w_{t+1} = (1 + r_{t+1}) s(w_t) + y_{t+1}

Linking to equations

Prepositional Logic

A proposition is a declarative sentence that is either true or false but not both

A atomic proposition is a simple statement, one that is not a combination of simpler statements

A compound proposition is a proposition, made up of two or more proposition joined by logical connective operators

logical connective operators: ¬\neg \wedge \lor \rightarrow \leftrightarrow

Truth Table for the negation of a Proposition

p ¬p\neg p
T F
F T

Truth Table for the Conjunction of Two Proposition

This is the And condition

p q pqp\wedge q
T T T
F T F
T F F
F F F

Truth Table for the Disjunction of Two Proposition

This is the inclusive OR condition

p q pqp \lor q
T T T
F T T
T F T
F F F

Exclusive OR

This is the exclusive OR condition

p q pqp\oplus q
T T F
F T T
T F T
F F F

Conditional Statements

Let p and q be propositions. The conditional statement pqp\rightarrow q is the proposition if p, then q The conditional statement pqp\rightarrow q is false when p is true and q is false, and true otherwise. In the conditional statement pqp\rightarrow q, p is called the hypothesis (or antecedent or premise) and q is called the conclusion (or consequence).

pqp\rightarrow q is a conditional statement or a implication q is true on the condition that q holds to put more bluntly: only when p is true, but q is false is the statement pqp\rightarrow q completely incorrect

"if it is raining, then the ground is wet."

"when it is not raining, then the state of the ground is doesn't matter we call this the vacuous case."

Definitions

Proposition
: pqp\rightarrow q A conditional statement
: "if it is raining, then the ground is wet"

Converse bdg-dangernot necessarily equivalent to the original proposition
: qpq\rightarrow p is the converse of pqp\rightarrow q
: > "if the ground is wet, then it is raining"
: "it could be wet for other reasons other than rain"

Inverse bdg-dangernot necessarily equivalent to the original proposition
: ¬p¬q\neg p\rightarrow\neg q is the inverse of pqp\rightarrow q
: > "if it is not raining, then the ground is not wet"
: "ground could be either wet or dry without rain"

Contrapositive bdg-infoequivalent to the original proposition
: ¬q¬p\neg q\rightarrow\neg p is the contrapositive of pqp\rightarrow q
: > " if the ground is not wet, then it is not raining "
: "because if it were raining then the ground will be wet"

Equivalent
: When two propositional statement have the same truth value

  Conditional Converse Contrapositive Inverse
pq pqp\rightarrow q qpq\rightarrow p ¬q¬p\neg q\rightarrow\neg p ¬p¬q\neg p\leftrightarrow\neg q
T T T T T T
T F F T F T
F T T F T F
F F T T T T

Biconditionals

The biconditional statement pqp\leftrightarrow q is the statement p if and only if also called bi-implication

p q pqp\leftrightarrow q
T T T
F T F
T F F
F F T

Precedence of Logical Operators

In compound propositions the order of precedence that we calculate is from left to right below

¬\forall \exists \neg \wedge \lor \rightarrow \leftrightarrow

Bitwise Operations

We can express true and false statements in terms of binary

p q pqp\wedge q pqp\lor q pqp\oplus q pqp\rightarrow q pqp\leftrightarrow q
1 1 1 1 0 1 1
1 0 0 1 1 0 0
0 1 0 1 1 1 0
0 0 0 0 0 1 1

Electronic Diagrams

Here is the logic propositions that the circuit is simulating:

  1. p1q1p1\wedge q1
  2. p2q2p2\lor q2
  3. p3(p3q3)p3\wedge (p3\lor q3)
  4. p4(p4q4)p4\lor (p4\wedge q4)
--- title: Logic Circuits --- stateDiagram-v2 [*] --> p1 p1 --> q1 q1 --> [*] [*] --> p2 [*] --> q2 p2 --> [*] q2 --> [*] [*] --> p3 p3 --> q3 p3 --> [*] q3 --> [*] [*] --> p4 p4 --> q4 q4 --> [*] p4 --> [*]

We see that AND circuits are basically serialized and OR circuits are parallel

Note how p(pq)pp(pq)p\wedge (p\lor q)\equiv p\equiv p\lor(p\wedge q) this is called the absorption law

Fuzzy Logic

Used in artificial intelligence

It means 1 for truth and 0 for false but there could be degrees between these two values for example 0.7 for Bill is happy means that it is usually true

Propositional Equivalence

pq¬p¬qpq\neg p\neg q pqp\rightarrow q ¬q¬p\neg q\rightarrow \neg p (pq)(¬p¬q)(p\rightarrow q)\leftrightarrow(\neg p\rightarrow \neg q)
1 1 0 0 1 1 1
1 0 0 1 0 0 1
0 1 1 0 1 1 1
0 0 0 1 1 1 1

Note that (pq)(¬p¬q)(p\rightarrow q)\leftrightarrow(\neg p\rightarrow \neg q) is true in all cases it's a tautology

This is becuase (pq)(¬p¬q)(p\rightarrow q)\equiv(\neg p\rightarrow \neg q)

p¬pp \lor \neg p is always true hence tautology and p¬pp \wedge \neg p is always false hence contradiction

Lecturer's example

Let Q(x,y):x2+y2=1Q(x, y):x^2+y^2=1

Let D1=R2=\set(x,y)x,yRD_1=\Bbb{R}^2=\set{(x,y)\mid x,y\in\Bbb{R}} all real numbers

D2=S1=\set(x,y)R2x=cosθ,y=sinθ,0θ<2πD_2=S^1=\set{(x,y)\in\Bbb{R}^2\mid x=\cos\theta,y=\sin\theta,0\leqslant\theta\lt 2\pi}
The unit circle in R2\Bbb{R}^2 centered at the origin

D3=\set(n,n)Z2nZ=diag(Z2)D_3=\set{(n,n)\in\Bbb{Z}^2\mid n\in \Bbb{Z}}=diag(\Bbb{Z}^2)

diagonal subspace of Z2\Bbb{Z}^2

Then lets evaluate the three DomainsD1,D2,D3D1: for all real numbers there are some that don’t work(x,y)D1,Q(x,y) is F(x,y)D1,Q(x,y) is TD2: this domain encompasses all values that work with unit circle(x,y)D2,Q(x,y) is T(x,y)D2,Q(x,y) is TD3: this domain encompasses all values that don’t work(x,y)D3,Q(x,y) is F(x,y)D3,Q(x,y) is FQ(n,n)=n2+n2=2n2=1iff n2=1/2n=±1/2nD3 \textcolor{hotpink}{\text{Then lets evaluate the three Domains}D_1,D_2,D_3}\\ \textcolor{Purple}{D_1:\ \text{for all real numbers there are some that don't work}}\\ \forall(x,y)\in D_1,Q(x,y)\space is\space F\\ \exists(x,y)\in D_1,Q(x,y)\space is\space T\\\\ \textcolor{Violet}{D_2:\ \text{this domain encompasses all values that work with unit circle}}\\ \forall(x,y)\in D_2,Q(x,y)\space is\space T\\ \exists(x,y)\in D_2,Q(x,y)\space is\space T\\\\ \textcolor{blueviolet}{D_3:\ \text{this domain encompasses all values that don't work}}\\ \forall(x,y)\in D_3,Q(x,y)\space is\space F\\ \exists(x,y)\in D_3,Q(x,y)\space is\space F\\\\ Q(n,n) = n^2+n^2=2n^2=1\\ iff\space n^2=1/2\therefore n=\pm 1/\sqrt{2}\\n\notin D_3

Quantifiers Over Finite Domains

Say the elements of a domain are x1,x2,...,xnx_1,x_2,...,x_n where nn is a positive integer then:

xP(x)P(x1)P(x2)...P(xn)\forall xP(x)\equiv P(x_1)\wedge P(x_2)\wedge ...\wedge P(x_n)

Or in other words the universal quantification is the same as the conjunction

xP(x)P(x1)P(x2)...P(xn)\exists xP(x)\equiv P(x_1)\lor P(x_2)\lor ...\lor P(x_n)

Or in other words the existential quantification is the same as the disjunction

Quantifiers Over Restricted Domains

The statement x<0(x2>0)\forall x\lt 0(x^2\gt 0) means "That for every negative real number the square of the negative real number is positive"

Binding Variables

When a quantifier is used on a variable say on xx, we say the occurrence of the variable is bound the converse is that the variable is free

Scope
: The part of a logical expression to which a quantifier is applied

Example

Statement: x(x+1=1)\exists x(x+1=1), so the variable xx is bound by the existential quantification x\exists x whilst the variable yy is free because it not bound by a quantifier and no value is assigned to this variable

Statement: x(P(x)Q(x))xR(x)\exists x(P(x)\wedge Q(x))\lor \forall xR(x), all the variables are bound

  1. the scope of the first quantifier x\exists x is the expression P(x)Q(x)P(x)\wedge Q(x) because x\exists x is applied only to P(x)Q(x)P(x)\wedge Q(x) and not the rest of the statement
  2. the scope of the second quantifier x\forall x is the expression R(x)R(x) because x\forall x is applied only to R(x)R(x) and not the rest of the statement

Logical Equivalence with Quantifiers

Show that x(P(x)Q(x))\forall x(P(x)\wedge Q(x)) and xP(x)xQ(x)\forall xP(x)\wedge \forall xQ(x) are equivalent
Assume the use of the same domain

  1. if x(P(x)Q(x))\forall x(P(x)\wedge Q(x)) is true, then xP(x)xQ(x)\forall xP(x)\wedge \forall xQ(x) is true
  2. if xP(x)xQ(x)\forall xP(x)\wedge \forall xQ(x) is true, then x(P(x)Q(x))\forall x(P(x)\wedge Q(x)) is true

bdg-dangercheck textbook solution to this is very wordy

Negating Quantified Expressions

Take Statement "Every student in class has taken a course in calculus" we can denote this as P(x)\forall P(x)

Say there does exist a student that hasn't taken calculus then you see we get the statement that

¬(xP(x))x¬P(x)\neg(\forall xP(x))\equiv\exists x\neg P(x)

Take the negation of the statement like "Every student in class has not taken a course in calculus" denoted as x ¬P(x)\forall x\ \neg P(x) this would be equivalent to statement "There does not exist a student who has taken a course in calculus" hence another get another equivalence

¬(x P(x))x ¬P(x)\neg(\exists x\ P(x))\equiv \forall x\ \neg P(x)

Nested Quantifiers

xy(x+y=0)\forall x\exists y(x+y=0)
which is the same thing as xQ(x)\forall xQ(x),
where Q(x)Q(x) is yP(x,y)\exists yP(x,y),
where P(x,y) is x+y=0P(x,y)\ is\ x+y=0\

bdg-whiteexample 1 Assume that the domain for the variables xx and yy consists of all real numbers
bdg-secondaryStatement xy(x+y=y+x)\forall x\forall y(x+y=y+x)
bdg-infosays xy(x+y=y+x)\forall x\forall y(x+y=y+x)

Negating

bdg-primaryNegating Nested Quantifiers

Let the universe of discourse be R\Bbb{R}
bdg-secondaryConsider Proposition xy(xy=1)\forall x\exists y(xy =1)
bdg-infoin wordsfor all xRx\in \Bbb{R}, there is a yRy\in\Bbb{R} such that xy=1xy=1

bdg-dangerNegate Proposition

Use De Morgan's Law

\forall x\exists y(xy=1)&\equiv\exists x\neg\{\exists y(xy=1)\}\\ &\equiv\exists x\forall y\neg(xy=1) \\ &\equiv\exists x\forall y(xy\neq 1)

bdg-dangerCounter-Example when x=0x=0 then 0×y=01,yR0\times y=0\neq 1,\forall y\in\Bbb{R} proposition is false

Negated Proposition on the other hand is true

Lecture Exercise 2 1.7
\neg(&\forall x\exists y\forall z(Q(x,y)\lor P(y,z)))\\ &\equiv\exists x\neg(\exists y\forall z(Q(x,y)\lor P(y,z)))\\ &\equiv\exists x\forall y\neg(\forall z(Q(x,y)\lor P(y,z)))\\ &\equiv\exists x\forall y\exists z\neg(Q(x,y)\lor P(y,z))\\ &\equiv\exists x\forall y\exists z(\neg Q(x,y)\wedge\neg P(y,z))\\
Exercises 1.5
  1. Translate these statements into English, where the domain for each variable consists of all real numbers.
    a) ∀x∃y(x < y)
    For all x there exists a y such that x < y
    b) ∀x∀y(((x ≥ 0) ∧ (y ≥ 0)) → (xy ≥ 0))
    For all x there are all y such that x greater or equal than 0 and y is greater or equal to 0 then the product of x and y is greater or equal than 0
    c) ∀x∀y∃z(xy = z)
    For all x and for all y there exists a z such that product of x and y is equal to z

    7 Let T(x, y) mean that student x likes cuisine y, where the
    domain for x consists of all students at your school and
    the domain for y consists of all cuisines. Express each of
    these statements by a simple English sentence.
    a) ¬T(Abdallah Hussein, Japanese)
    Abdullah Hussein does not like Japanese cuisine
    b) ∃xT(x, Korean) ∧ ∀xT(x, Mexican)
    There exists a student at my school who like Korean and all students at my school like Mexican
    c) ∃y(T(Monique Arsenault, y) ∨ T(Jay Johnson, y))
    There exists a cuisine that Monique Arsenault likes or Jay Johnson like a that cuisine
    d) ∀x∀z∃y((x ≠ z) → ¬(T(x, y) ∧ T(z, y)))
    For all students at my school and another group of people who are not students a my school there exists a cuisine where it is untrue That a student and a non-student loves
    e) ∃x∃z∀y(T(x, y) ↔ T(z, y))
    there exists a student at my school and a z proposition for all cuisines where th student and thier favourite cuisine is true if and only if the z condition has the likes
    f ) ∀x∀z∃y(T(x, y) ↔ T(z, y))

    25 Translate each of these nested quantifications into an En-
    glish statement that expresses a mathematical fact. The
    domain in each case consists of all real numbers.
    a) ∃x∀y(xy = y)
    There exists a x for every y such that the product of x and y is y x=1
    b) ∀x∀y(((x < 0) ∧ (y < 0)) → (xy > 0))
    for all x and all y if x is greater than 0 and y is negative then x times y is greater than 0
    c) ∃x∃y((x^2 > y) ∧ (x < y))
    there exists a x and there exists a y such that the square of x is greater than y and x is less than y
    d) ∀x∀y∃z(x + y = z)
    there exists a x and there exists a y and there exists a z such that x plus y is equal to z

    27 Determine the truth value of each of these statements
    if the domain of each variable consists of all real num-
    bers.
    a) ∀x∃y(x^2 = y) T
    b) ∀x∃y(x = y^2 ) T
    c) ∃x∀y(xy = 0) T for y = 0
    d) ∃x∃y(x + y ≠ y + x) F\ supposed to be false
    e) ∀x(x ≠ 0 → ∃y(xy = 1)) T
    f) ∃x∀y(y ≠ 0 → xy = 1) T
    g) ∀x∃y(x + y = 1) T for negative numbers
    h) ∃x∃y(x + 2y = 2 ∧ 2x + 4y = 5) T
    i) ∀x∃y(x + y = 2 ∧ 2x − y = 1) T
    x = 2 -y
    2(2 -y) − y = 1
    4 - 2y = 1
    j) ∀x∀y∃z(z = (x + y)∕2) T

    30 .Rewrite each of these statements so that negations ap-
    pear only within predicates (that is, so that no negation
    is outside a quantifier or an expression involving logical
    connectives).
    a) ¬∃y∃xP(x, y)
    b) ¬∀x∃yP(x, y)
    c) ¬∃y(Q(y) ∧ ∀x¬R(x, y))
    d) ¬∃y(∃xR(x, y) ∨ ∀xS(x, y))
    e) ¬∃y(∀x∃zT(x, y, z) ∨ ∃x∀zU(x, y, z))

    31 Express the negations of each of these statements so that
    all negation symbols immediately precede predicates.
    a) ∀x∃y∀zT(x, y, z)
    b) ∀x∃yP(x, y) ∨ ∀x∃yQ(x, y)
    c) ∀x∃y(P(x, y) ∧ ∃zR(x, y, z))
    d) ∀x∃y(P(x, y) → Q(x, y))

    32 Express the negations of each of these statements so that
    all negation symbols immediately precede predicates.
    a) ∃z∀y∀xT(x, y, z)
    b) ∃x∃yP(x, y) ∧ ∀x∀yQ(x, y)
    c) ∃x∃y(Q(x, y) ↔ Q(y, x))
    d) ∀y∃x∃z(T(x, y, z) ∨ Q(x, y))

    33 Rewrite each of these statements so that negations ap-
    pear only within predicates (that is, so that no negation
    is outside a quantifier or an expression involving logical
    connectives).
    a) ¬∀x∀yP(x, y)
    b) ¬∀y∃xP(x, y)
    c) ¬∀y∀x(P(x, y) ∨ Q(x, y))
    d) ¬(∃x∃y¬P(x, y) ∧ ∀x∀yQ(x, y))
    e) ¬∀x(∃y∀zP(x, y, z) ∧ ∃z∀yP(x, y, z))

    40 Find a counterexample, if possible, to these universally
    quantified statements, where the domain for all variables
    consists of all integers.
    a) ∀x∃y(x = 1∕y)
    b) ∀x∃y(y 2 − x < 100)
    c) ∀x∀y(x 2 ≠ y 3 )

    45 Determine the truth value of the statement ∀x∃y(xy = 1)
    if the domain for the variables consists of
    a) the nonzero real numbers.
    b) the nonzero integers.
    c) the positive real numbers.\

Rules of Inference

Proofs
: In mathematics these are valid arguments that establish the truth of a mathematical statement

Arguments
: A sequence of statements that end with a conclusion

Valid
: The conclusion or final statement of the arguments follows from the truth of the preceding statements or premises of the arguments

Rules of Inferences
: These are the templates or basic tools for establishing the truth of statements

Fallacies
: Incorrect reasoning that may lead to incorrect conclusions

Lemma
: a simple theorem

Corollary
: A direct result of the theorem (special case etc)

Conjecture
: A statement whose truth value is unknown

Argument Form

Consider the following arguments which by definition is a sequence of propositions

"If you have access to the internet, then you can change your grade"
"You have access to the network"
therefore
"You can change your grade"

(pq)pq it’s a tautology(p\rightarrow q)\wedge p\rightarrow q\ \textcolor{Goldenrod}{\text{it's a tautology}}

So a argument is a proposition of the form

p1p2p3...pnq p_1\wedge p_2\wedge p_3\wedge ... \wedge p_n \rightarrow q

Propositions
: are what p1p2p3...pnp_1\wedge p_2\wedge p_3\wedge ... \wedge p_n called

Hypothesis
: is what qq is called

Above is what defines being a valid argument meaning all the premises are true so the conclusion follows as well because it means the hypothesis is true or when the statement is a tautology

Rules of Inference

Modus Ponens

Modus Tolens

Hypothetical Syllogism

Disjunctive Syllogism

Resolution

Let us examine it

pq¬pq¬pr¬pr p\lor q\equiv\neg p\rightarrow q\\ \neg p\lor r\equiv\neg p\rightarrow r

Start with proposition p
if it is true then we conclude r\
if it is false then we conclude q
the proposition p leads to q or r

Rules of Inference for Quantified Statements

Universal Instantiation
Universal Generalization
Existential Instantiation
Existential Generalization

Mathematical Proofs

Axioms or Postulates
: statements that are assumed to be true used in proofs

We consider 5 types of proofs

  1. Direct Proof - show pqp\rightarrow q is true
  2. Indirect Proof - prove that the contrapositive ¬q¬p\neg q\rightarrow\neg p is true
  3. Proof by contradiction - To prove ptpt show ¬pF\neg p\rightarrow F is true
  4. Proof by cases
  5. Proof of Equivalences

Direct Proof

The implication pqp\rightarrow q can be proved to be true by showing that if p is true then q is true

This means the combination of pTp\equiv T or qFq\equiv F never occurs

Example

bdg-primary-linetheorem if n is an even integer, then n3n^3 is an even integer

bdg-secondary-lineproof bdg-plaindirect
Let nn be an even integer. Then by definition, kZ\exists k\in\Bbb{Z} such that n=2kn=2k
Now: n3=(2k)3=23k3=2(4k3)n^3=(2k)^3=2^3k^3=2(4k^3) Since, 4k3Z4k^3\in\Bbb{Z}, we have n3n^3 an even integer

bdg-primary-linetheorem if nn is an odd, then n2nn^2-n is an even

bdg-secondary-lineproof bdg-plaindirect
Let nn be an odd. Then by definition, kZ\exists k\in\Bbb{Z} such that n=2k=1n=2k=1
Now: n2n=(2k+1)2(2k+1)=4k2+4k+12k1=4k2+2k=2(2k2+k)n^2-n=(2k+1)^2-(2k+1)=4k^2+4k+1-2k-1=4k^2+2k=2(2k^2+k) Since, 2k2+kZ2k^2+k\in\Bbb{Z}, we have n2nn^2-n is even

bdg-danger-lineaxiom Assume the fact that 3n is even iff n even
bdg-primary-linetheorem n is an even integer iff 3n + 5 is odd

bdg-secondary-lineproof bdg-plaindirect
Let nn be an odd. Then by definition, kZ\exists k\in\Bbb{Z} such that n=2k=1n=2k=1
Now: n2n=(2k+1)2(2k+1)=4k2+4k+12k1=4k2+2k=2(2k2+k)n^2-n=(2k+1)^2-(2k+1)=4k^2+4k+1-2k-1=4k^2+2k=2(2k^2+k) Since, 2k2+kZ2k^2+k\in\Bbb{Z}, we have n2nn^2-n is even

Indirect Proof

Proof by Contradiction

Proof by Cases

In this method proves theorems of the form
P=(p1p2...pn)qP=(p_1\lor p_2\lor ...\lor p_n)\rightarrow q

We prove that piq,i=1,2,3,...,np_i\rightarrow q,\forall i=1,2,3,...,n and use the tautology

(p1p2...pn)[(p1q)...(pnq)](p_1\lor p_2\lor ...\lor p_n)\leftrightarrow[(p_1\rightarrow q)\lor ...\lor(p_n\rightarrow q)]

Proof of Equivalences

Here we show everything is equivalent we could use a circle of implications

p1p2...p2p1p_1\rightarrow p_2\rightarrow ...\rightarrow p_2\rightarrow p_1